package 力扣._100048_美丽塔2;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Solution2 {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        //暴力，但只遍历极大值点
        List<Integer> maxlist = new ArrayList<>();
        for (int i = 1; i < maxHeights.size() - 1; i++) {
            if (maxHeights.get(i) > maxHeights.get(i - 1) && maxHeights.get(i) > maxHeights.get(i + 1))
                maxlist.add(i);
        }
        maxlist.add(0);
        maxlist.add(maxHeights.size() - 1);

        long max = -1;
        for (int j : maxlist) {
            //向两边单调不增
            long sum = maxHeights.get(j);
            //向左
            long last = sum;
            for (int i = j - 1; i >= 0; i--) {
                if (maxHeights.get(i) >= last)
                    sum += last;
                else {
                    last = maxHeights.get(i);
                    sum += last;
                }
            }
            //向右
            last = maxHeights.get(j);
            for (int i = j + 1; i < maxHeights.size(); i++) {
                if (maxHeights.get(i) >= last)
                    sum += last;
                else {
                    last = maxHeights.get(i);
                    sum += last;
                }
            }
            max = Math.max(max, sum);
        }

        return max;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(5);
        list.add(5);
        list.add(6);
        list.add(6);
        list.add(6);
        list.add(1);
        long l = new Solution2().maximumSumOfHeights(list);
        System.out.println(l);
        Random random = new Random();
        int i = random.nextInt();

    }
}
